package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

public class FlattenBinaryTreeToLinkedList {

    /**
     * 寻找先驱节点，然后将左子树的顶点到前驱节点的路径插入到当前节点的右子树中
     */
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left != null){
                TreeNode pre = root.left;
                while (pre.right != null){
                    pre = pre.right;
                }
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }



    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(7,-10,2,-4,3);
        PrintUtils.println(root);
        new FlattenBinaryTreeToLinkedList().flatten(root);
        PrintUtils.println("==============");
        PrintUtils.println(root);
    }
}
